package leetcode

import kotlinetc.println

//https://leetcode.com/problems/sudoku-solver/

/**
Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.'.
 */
fun main(args: Array<String>) {
    val sudoku = arrayOf(
            charArrayOf('5', '3', '.', '.', '7', '.', '.', '.', '.'),
            charArrayOf('6', '.', '.', '1', '9', '5', '.', '.', '.'),
            charArrayOf('.', '9', '8', '.', '.', '.', '.', '6', '.'),
            charArrayOf('8', '.', '.', '.', '6', '.', '.', '.', '3'),
            charArrayOf('4', '.', '.', '8', '.', '3', '.', '.', '1'),
            charArrayOf('7', '.', '.', '.', '2', '.', '.', '.', '6'),
            charArrayOf('.', '6', '.', '.', '.', '.', '2', '8', '.'),
            charArrayOf('.', '.', '.', '4', '1', '9', '.', '.', '5'),
            charArrayOf('.', '.', '.', '.', '8', '.', '.', '7', '9')
    )

    solveSudoku(sudoku)



}

fun solveSudoku(board: Array<CharArray>): Unit {

    solveDfs(board, 0, 0)

}

//深度优先遍历
fun solveDfs(board: Array<CharArray>, row: Int, col: Int): Boolean {

    if (row >= 9) return true//到了最后一行+1

    if (col >= 9) return solveDfs(board, row+1, 0)


    if (board[row][col] == '.') {
        for (i in 1..9) {
            board[row][col] = (i + '0'.toInt()).toChar()
            if (isValidSodoku(board, row, col)) {
                if (solveDfs(board, row, col + 1)) return true
            }
            board[row][col] = '.'
        }
    } else
        return solveDfs(board, row, col + 1)

    return false
}

fun isValidSodoku(board: Array<CharArray>, row: Int, col: Int): Boolean {

    for (i in 0 until 9)
        if (i != col && board[row][col] == board[row][i]) return false
    for (i in 0 until 9)
        if (i != row && board[row][col] == board[i][col]) return false

    val m = 3 * (row / 3)
    val n = 3 * (col / 3)

    for (i in m until m + 3)
        for (j in n until n + 3)
            if ((i != row || col != j) && board[row][col] == board[i][j]) return false

    return true
}



